{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f1a0e5c7",
   "metadata": {},
   "source": [
    "## k 路归并排序\n",
    "\n",
    "将k个有序数组合并为一个有序数组。\n",
    "分为两个过程：\n",
    "    1. 生成待测试数据 -> create_k_sorted_arrays(k, n)\n",
    "    2. 编写k路归并算法并检验 -> merge_sorted_arrays(arrays)\n",
    "\n",
    "**生成数据**：\n",
    "初始化：\n",
    "    1. 首尾指针，初始化列表\n",
    "    2. 循环体遍历的条件\n",
    "    3. 算法循环的逻辑\n",
    "\n",
    "arr_count, k路计数器\n",
    "arrays 列表 -> 其内部的元素是列表\n",
    "\n",
    "**k路归并排序**：\n",
    "    1. 函数递归返回条件\n",
    "    2. 将列表内的元素进行二分: first_half, second_half\n",
    "    3. 对二分后的列表进行递归调用\n",
    "    4. 函数排序功能逻辑： ->\n",
    "        1. 初始化 ：left_ptr, right_ptr, merged_array\n",
    "        2. 元素比较与排序\n",
    "        3. 返回列表\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d18072e1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1  2  3  4  5  6  7  8  9 10]\n",
      "[11 12 13 14 15 16 17 18 19 20]\n",
      "[21 22 23 24 25 26 27 28 29 30]\n",
      "[31 32 33 34 35 36 37 38 39 40]\n"
     ]
    }
   ],
   "source": [
    "## 生成数据\n",
    "import numpy as np\n",
    "def create_k_sorted_arrays(k, n):\n",
    "    begin = 1\n",
    "    end = n + 1\n",
    "    arrays = []\n",
    "    if k == 0 or n == 0:\n",
    "        return arrays\n",
    "    \n",
    "    arr_count = 1\n",
    "    while arr_count <= k:\n",
    "        array = np.arange(begin, end)\n",
    "        arrays.append(array)\n",
    "        arr_count += 1\n",
    "        begin = end \n",
    "        end = arr_count * n + 1\n",
    "    return arrays\n",
    "\n",
    "arrays = create_k_sorted_arrays(4, 10)\n",
    "# print(arrays)\n",
    "for i in range(len(arrays)):\n",
    "    print(arrays[i])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "296ec848",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The final result is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40].\n"
     ]
    }
   ],
   "source": [
    "## 归并排序\n",
    "\n",
    "def merge_sorted_array(arrays):\n",
    "    if len(arrays) == 0:\n",
    "        return arrays\n",
    "    if len(arrays) == 1:\n",
    "        return arrays[0]\n",
    "    \n",
    "    fist_half = arrays[0:int(len(arrays) / 2)]\n",
    "    second_half = arrays[int(len(arrays) / 2):]\n",
    "\n",
    "    left_array = merge_sorted_array(fist_half)\n",
    "    right_array = merge_sorted_array(second_half)\n",
    "\n",
    "    left_ptr = 0\n",
    "    right_ptr = 0\n",
    "    merged_array = []\n",
    "    while left_ptr < len(left_array) and right_ptr < len(right_array):\n",
    "        if left_array[left_ptr] <= right_array[right_ptr]:\n",
    "            merged_array.append(left_array[left_ptr])\n",
    "            left_ptr += 1\n",
    "        elif right_array[right_ptr] < left_array[left_ptr]:\n",
    "            merged_array.append(right_array[right_ptr])\n",
    "            right_ptr += 1\n",
    "        if left_ptr >= len(left_array):\n",
    "            merged_array.extend(right_array[right_ptr:])\n",
    "            break\n",
    "        elif right_ptr >= len(right_array):\n",
    "            merged_array.extend(left_array[left_ptr:])\n",
    "            break\n",
    "    return merged_array\n",
    "\n",
    "final_array = merge_sorted_array(arrays)\n",
    "print(\"The final result is {0}.\".format(final_array))\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
